백준 1644번

오늘 풀어본 문제는 백준의 1644번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

$3$ : $3$ (한 가지)
$41$ : $2+3+5+7+11+13 = 11+13+17 = 41$ (세 가지)
$53$ : $5+7+11+13+17 = 53$ (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, $20$ 이 그 예이다. $7+13$ 을 계산하면 $20$ 이 되기는 하나 $7$ 과 $13$ 이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, $3+5+5+7$ 과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 $N$ 이 주어진다. $(1 \le N \le 4,000,000)$

출력

첫째 줄에 자연수 $N$ 을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

풀이과정

1번째 시도

문제를 해결하기 위해 시도한 방법은 다음과 같다.

에라토스테네스의 체를 활용하여 소수들을 미리 구한다.
소수들의 누적 합을 저장한다.
투 포인터를 활용하여 부분합이 $N$ 의 되는 가짓수를 구한 뒤 출력한다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    const ull inputRange = 4000000ULL;
    vector<bool> isPrime(inputRange + 1, true);

    isPrime[0] = false;
    isPrime[1] = false;

    for (ull curr=2; curr<=inputRange; curr++) {
        if (isPrime[curr]) {
            for (ull multiple=curr*curr; multiple<=inputRange; multiple+=curr) {
                isPrime[multiple] = false;
            }
        }
    }

    int N;
    cin >> N;

    vector<int> prefixSum;

    int sum = 0;
    prefixSum.emplace_back(0);

    for (int i=2; i<=inputRange; i++) {
        if (isPrime[i]) {
            sum += i;
            prefixSum.emplace_back(sum);
        }
    }

    int start = 0;
    int end = 1;

    int result = 0;

    while (start < end && start < prefixSum.size() && end < prefixSum.size()) {
        int curr = prefixSum[end] - prefixSum[start];

        if (curr < N) {
            end++;
        }
        else if (curr > N) {
            start++;
        }
        else {
            result++;
            start++;
            end++;
        }
    }

    cout << result;

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

생각보다 문제가 쉽게 일찍 풀려서 다행이었다. 투 포인터를 이용하는 문제도 조금씩 적응되기 시작한 것 같다. 그래도 꾸준히 문제를 풀어온 덕분인걸까? 모든 문제가 오늘 같이 잘 풀리는 문제면 좋겠다!

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1644

← Previous Post Next Post →